On Benes Rearrangeable Networks
By F. K. HWANG
(Manuscript received July 31, 1970)
V. E. Benel considered a class of multi-stage switching networks 1 and
proved that if the linkage pattern between two stages is chosen in a specific
way, then the resulting networks are rearrangeable. We offer a simpler
proof by pointing out the relation between Benel class networks and the
Slepian-Duguid Theorem on three-stage Clos networks.
I. INTRODUCTION
V. E. Benes 1 considered the class, denoted here by /*(%, n?, . . .
nt + i), of all connecting networks v with the following properties:
(i) v is two sided, with N terminals on each side where N = H \1\ n % .
(ii) v is built of an odd number s = 2t + 1 of stages f* ,
k = 1, • • • 2t + 1 connected as specified by permutations
<pi , • • • <p2« • In the notation of BeneS,
" — fi^ifa * " ' Vaifai + i •
(Hi) f k consists of N/n k identical square switches of size n k .
(iv) ft = f 2 < + 2-t for k = 1, • ■ • t.
Bene§ proceeded to prescribe a specific way of choosing <p k (See
page 113 of Ref 1):
"Order the switches of each stage; to define <p k for a given 1 S k ^ t,
take the first switch of f* , say with n k outlet and n k a divisor of N,
and connect these outlets one to each of the first n k switch of f*+i ;
go on to the second switch of f * and connect its n k outlets one to each
of the next n k switches of f A+ i ; when all the switches of f*+i have one
link on the inlet side, start again with the first switch; proceed cyclically
in this way till all the outlets of f t are assigned."
BeneS also specified <p k = <p 3 , + 1 _ t for A; = t + 1, • • • 2t. We call a
network v c B(n t , n 2 , • ■ • n f + 1 ) constructed in this manner a cyclic
Bene§ network.
201
202 THE BELL SYSTEM TECHNICAL JOURNAL, JANUARY 1971
Benes proved that a cyclic Benes network is rearrangeable. The
proof given by Benes in Ref. 1 is, however, quite lengthy and involved.
In the present work, we offer an alternate proof by pointing out the
links between cyclic Benes networks and the Slepian-Duguid Theorem
on three-stage Clos networks. It is hoped that the simpler proof will
lead to new insights into the problem of constructing rearrangeable
networks.
II. MULTISTAGE REARRANGEABLE NETWORKS
We show a way to construct v e B(rii , n 2 , ■ • • n l + l ) from v' t
B(n 2 ,n 3 , • • • ?i, +0 such that if v' is rearrangeable then v is rearrangeable.
We construct a three-stage network by having the first stage and
the third stage each consist of N/n* copies of n x X n x square switches,
A x ■ • • A N/ni , Ci ■ ■ • C N/ni say, where the second stage consists of
n x copies of v' ', say, B x , ■ ■ ■ B ni . Each switch in the first stage and the
third stage is then linked to every 5, in the second stage. (It does not
matter which inlet or outlet of 5, is finked to which A, or which C,- .)
This gives a network v e B(?ii , n 2 , • • • n l+1 ). Now if v' is also con-
structed in this manner and so on down to the three-stage network,
we then call v a Bene§ network. That a Bene§ network is rearrangeable
will follow from a multistage version of the Slepian-Duguid Theorem
on three-stage Clos networks. To be complete, we state this multistage
version and give a proof.
Theorem. 1: Let v e B{n x , n 2 , • • • n, + I ) be a Benes network. Then v is
rearrangeable.
Proof: For t = 0, we have a special case of awi X n x square switch
which is clearly rearrangeable and no construction is needed. Supposing
that Theorem 1 is true for t' = t — 1 ^ 0, we prove Theorem 1 for
t' = t.
A maximal assignment between each inlet terminal and each outlet
terminal is a permutation tp of the set of numbers [i : i = 1,2, • • • N}
where iV = XI /-J n > ■ (Following Bene§, we need only consider maximal
assignments.) A given maximal assignment can also be viewed as a
set of defining relationships between each switch in the first stage and
each switch in the third stage (treating the set of v' as the second
stage). Set N 2 = n 2 • n 3 • • • ■ n t+1 , note that N = thNt . Let A, be
the ith. switch in the first stage, A = [ A { : % = 1, 2, • • • N a ] and C f
be the jth. switch in the third stage, C = {C,- : j = 1, 2, • • • N 2 }. Con-
sider a particular first stage switch A, . Suppose the n x inlet terminals of
REARRANGEABLE NETWORKS
203
A { are assigned by <p to third-stage outlet terminals, y lX , y i2 , ■ ■ • y<» •
Denote by Y ih (Y ik t C) the third-stage switch that contains y ik , k =
1, 2, -Jh, and let S t = { Y ik : k = 1, 2, • • • n x } . Since U?-i & has
a total of aj-ni elements and since each distinct element has only n x
repetitions, there are at least x distinct elements in {JUi 8 t for each
x = 1,2, ••■ N 2 . Hence the condition of P. Hall's Theorem 2 on distinct
representation of subsets is satisfied and there exists a set Z = \Z t :i =
1, 2, • • • N 2 } such that Z, e S t and Z = C. Then &< , i = 1, • • • N 2
can be chosen such that x t e A,- , <px { e Z, . Now we may choose to route
the rii calls x { -» pre,- through the first second-stage switch Bj , which
by induction hypothesis is rearrangeable. The problem is then reduced
to that of a maximal assignment in a network of type B{n x — 1, n 2 , ••■
n l+ i). By repeatedly applying the same argument, we obtain sub-
assignments on each B k .
III. CYCLIC BENES NETWORKS
Theorem 2: Every cyclic Benel network is a Benes network, hence is
rearrangeable.
Proof: A single stage cyclic Benes network is a N X N square matrix,
which is a Benes network. Suppose Theorem 2 is true for (2t — 1)
stage network where t ^ 1. We prove a (2t + 1) stage cyclic Bene§
network is a Bene§ network.
Let v = S^U ■ • • Pxfii+i £ Bin! , n 2 , • • • n t+1 ) be a cyclic Benes
network. We shall show that the complex p = £ 2 (p 2 {a ■ ■ ' <p 2 t-i^2i
can be decomposed into n x copies of v where v' t B(n 2 , n 3 • • • n t+1 )
is also a cyclic Beneg network. Furthermore <p x and <p 2t are such that
each switch in ti and f 2t+ i is linked to each v' as is required by the
definition of a Benes" network. By our inductive hypothesis, v' is a
Benes network. This is enough to prove that v is a Benes network.
Let the notation [AftM\ denote a set of switches A e f , in the
network <r. Similarly, let {J3/f i+1 (cr)} denote a set of switches B e f <+ ,
in <r. We define a relation R on the two sets A and 5 and write
\A/UW)}B{Bn i+ M\
if every switch of A is linked to every switch of B in the network <r.
For the cyclic Benes network v = Cm& * ' " w«C«+i > let tne switches
in each stage be ordered. Note that the p< , for i = 1, 2, • • • t, in ? can
be described by,
|.T.(mod /.O/r.Wl^ln.^ - 1) + Z, : h = 1, 2, • • • n,/r« + iM)
204 THE BELL SYSTEM TECHNICAL JOURNAL, JANUARY 1971
for
x = 1,2, ■••/,• where /, = AT/n,n t+I ,
and
<Pi = <P2t+i-i for i = t -\- 1, • • • 2t.
Decompose the compex P = fa^fa '" <pit-\Z,it into {v\ , v 2 , ■■■
Vn j where v» , A = 1, 2, ■ • • ni , consists of those sets of switches:
\h(modnd/t»(v)]
\(h - i) fi«* + m *-™* = i. 2, • • • rK-/r*(v)|
for fc = 3, 4, •■ • 2t - 1
and
{/i(modni)/f 2< (j')}.
Then clearly v h e 5(n 2 , n 3 • • • n,+i), A = 1, 2, • • • n x .
In each v h , let the switches in each stage be ordered as is consistent
with their orderings in v. Suppose s, is a switch e f,(p A ) and g\ its co-
ordinate in v h (i.e., s, is the grj tb switch in f,(v*))- Then s, e f,(i>) and
has the coordinate g { in v.
If we write g' { uniquely as
g > = C n "i + <*« for C ^ 0, 1 ^ eft ^ ft »* (1)
J -2 j-2
(using the convention J]n f = 1 if i = 2 J
then 0,- can be uniquely written as
<7, = C ffn, + # + (h - 1) fin,- . (2)
;=1
Vice versa, if s, e £.•("), z ^ 1, 2f + 1, has coordinate #, as expressed
in equation (2), then s, is also a switch in f <(»»») with coordinate <7<
as expressed in equation (1).
Next we show that v h is a cyclic Bene§ network, i.e., let v h =
f^fa • • • <P2t-\$2t> then <p t , i = 2, 3 • • • t can be described by
{s'(mod /O/tfMWn.Cr/ - 1) + h : Z, = 1, 2. • • • n,/rt + i(i*)} (3)
for
x' = \,2, ••• /<
REARRANGEABLE NETWORKS 205
where
/' = N'/n t n t+1 and N' = N fn, ,
and
<Pk = <P2i+i-k for k = t + 1, ■ • • 2t — 1.
(Note that in equation (3), the two sets of switches are written in
coordinates g' of v h .) From equations (1) and (2),
i-i
g . = mgl - (n, - m + (h - 1) II n, . (4)
Let s, c f{("„) be a switch having coordinate g' t = x' (mod fj). Then
we have the unique expression
g '. = g ./j + x' for some g ^ 0. (5)
Since HjlJ n, divides /J, from equations (1) and (5), there exists
a unique u, g u ^ II)-i+i n i > such that
x' = wlln, + ^. (6)
»-2
From equation (4), the corresponding g { is
i-l
g . = nMVi + *') - fa ~ Wi + (h-l)Jln i
i-l
= qnj'i + W - (n, - l)d{ + (h - 1) IK
= qh + x (7)
where /, = n x /J and
i-l
x = niX ' - ( ni - l)dj + (A - 1) II w,
1-2
= niu- n n,- + d{) - (n, - l)d{ + (h - 1) II n, , by (5)
\ ,_2 / ' -2
= ii-ii»i +« + (*- 1) n»* • (8)
i-i
It can be easily verified that ^ x < /, .
Equation (7) says that a switch s< e f*(v») which has coordinate
0< = z{ (mod /{) has coordinate g = x (mod /<) in v.
Next we show that if the two sets {G' i+ i/ti+M} and {GWfr+iCO)
206 THE BELL SYSTEM TECHNICAL JOURNAL, JANUARY 1971
are such that
{.r'(mod /O/tfWMflWrt+ito) (9)
and
{z(mod WUtiWQi+itti+ify)} (10)
hold, then G' i+J and G i+1 are coordinates of the same set of switches.
Equation (9) implies
(cwtf+ifa)}
= Mx' - 1) + U : h , = 1, 2, • - . */#„&)!,
- {»«(«• n »f + d' t - lj + Z,. : U - 1, 2, • • • n^tfrtk)} ,
- { w II ^ + (# - IK- + Z, : l { - 1, 2, .-. ni/tf+ifo)}-
Equation (10) implies
{GWft+ifr)) = {n { (x - 1) + l t : U = l, 2, • • • n,/r. +1 (^)},
- {»<(«■ n»* + « + Qt - 1) n^,- - 1)
+ h:l<= l,2,..-n,/f,- +1 (,)|,
{w Iln,- + (d'i - l)n t + (h - 1) fln y
V j' = l ,_ 2
+ Z« :Z, = 1,2, -•-m/ft+iO')}-
- SW
But from equation (2), if ^ = h ![*■.■»# + (<*J - IK + Z, , 1 g Z, ^ n if
then its corresponding #-,- is
i
Q* = wll>/ + («*' - 1)»« + Z, + (A - 1) fin,- .
Therefore [G' i+ i/?UM)} and [GWiWiMi are clearly coordinates
of the same set of switches.
That each switch in f x (i») is linked to each v' h by < Pl is a direct result of
{z(mod 1^/tM\E[ni{x - 1) + h : h = 1, 2, • • ■ ih/r,(r)J
since
REARRANGEABLE NETWORKS
207
[h(mod U)\ n [ni(x - 1) + k : h - 1, 2, • • • %} | - 1
for each A = 1, 2, • • • n x .
Since v = faiti ■ ■ ' <p2«r 2 « +l is symmetric with respect to its middle
stage, and v h z B(n 2 , n 3 , • • • n t + l ), clearly <p' k = <^ (+ i_* for fc = t + 1,
• • • 2t — 1. And finally, again by an argument of symmetry, each
switch in f 2 « + i is linked to each p' h by <p 2l .
REFERENCES
1. Benes, V. E., Mathematical Theory of Connecting Networks and Telephone
Traffic, Chapter 3, New York: Academic Press, 1965.
2. Hall, P., "On Representative of Subsets," J. London Math. Soc, 10 (1935), pp.
26-30.